The present invention relates to techniques for providing one-shot verifiable encryption utilizing lattice problems.
Verifiable encryption allows one to prove properties about encrypted data and is an important building block in the design of cryptographic protocols, for example, group signatures, key escrow, fair exchange protocols, etc. Existing lattice-based verifiable encryption schemes, and even just proofs of knowledge of the encrypted data, require parallel composition of proofs to reduce the soundness error, resulting in proof sizes that are only truly practical when amortized over a large number of ciphertexts.
Lattice problems may be used for cryptographic systems because they may offer better security than discrete logarithm and factoring based problems. Efficient lattice-based constructions are known for signature and encryption schemes. Lattice cryptography has matured to the point where it appears that any cryptographic operation that can be performed based on any other technique can also be performed based on a lattice technique.
Lattice-based public-key encryption schemes and digital signature schemes, based on NTRU and Ring-LWE problems, are essentially as practical as the non-lattice based ones. All keys and outputs are less than 1 kilobyte for 128 bits of security. Slightly more advanced operations, such as identity-based encryption, can be implemented with keys and ciphertexts being around 4 kilobytes, and blind signatures have outputs of around 100 kilobytes. Other operations, however, are usually less practical.
One such operation is public-key encryption with proofs of plaintext knowledge, which allow the encryptor to create a non-interactive zero-knowledge proof of knowledge of the plaintext contained in a given ciphertext. For example, suppose that a sender encrypted a plaintext into a ciphertext using a public key. Proof of plaintext knowledge allows the sender to convince a receiver, who does not have the secret key, that the sender knows the plaintext. Zero-knowledge proofs are those in which the proof of plaintext knowledge does not reveal any information about the plaintext to the receiver. Verifiable encryption with respect to a binary relation on the plaintext is a zero-knowledge proof on the public inputs including the private key, the ciphertext, and the binary relation, that allows the sender to convince the receiver that the ciphertext is an encryption of the plaintext using the public key. Conventional proofs of plaintext knowledge for lattice-based encryption schemes may use the adaptation of Sterns protocol or the single-bit-challenge version of the lattice-based Fiat-Shamir protocol. However, these conventional schemes have soundness errors, requiring the proof to be repeated, for example, 128 times, to reduce the soundness errors to a negligible quantity.
Accordingly, a need arises for techniques for performing public-key encryption with proofs of plaintext knowledge using a lattice-based scheme that provides improved efficiency over conventional techniques.